#ifndef __MY_QUEUE_H__
#define __MY_QUEUE_H__

#include <cstddef>
#include <stdexcept>

template <typename T>
struct QueueNode
{
    T data;
    QueueNode<T>* next;

    QueueNode<T>(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class Queue
{
  public:
    Queue();
    ~Queue();

    void push(const T& data);

    void push(T&& data);

    void pop();

    T top() const;

    bool empty() const;

    size_t size() const;

  private:
    QueueNode<T>* front;
    QueueNode<T>* rear;
    size_t count;
};

template <typename T>
Queue<T>::Queue() : front(nullptr), rear(nullptr), count(0)
{
}

template <typename T>
Queue<T>::~Queue()
{
    while (front != nullptr)
    {
        QueueNode<T>* tmp = front->next;
        delete front;
        front = tmp;
    }

    front = rear = nullptr;
    count = 0;
}

template <typename T>
void Queue<T>::push(const T& data)
{
    QueueNode<T>* node = new QueueNode<T>(data);

    if (rear)
    {
        rear->next = node;
        rear = node;
    }
    else
    {
        front = rear = node;
    }
    count++;
}

template <typename T>
void Queue<T>::push(T&& data)
{
    QueueNode<T>* node = new QueueNode<T>(std::move(data));

    if (rear)
    {
        rear->next = node;
        rear = node;
    }
    else
    {
        front = rear = node;
    }
    count++;
}

template <typename T>
void Queue<T>::pop()
{
    if (empty())
    {
        throw std::runtime_error("queue is empty");
    }

    QueueNode<T>* tmp = front->next;
    delete front;
    front = tmp;
    count--;

    if (empty())
    {
        rear = nullptr;
    }
}

template <typename T>
T Queue<T>::top() const
{
    if (empty())
    {
        throw std::runtime_error("queue is empty");
    }
    return front->data;
}

template <typename T>
bool Queue<T>::empty() const
{
    return count == 0;
}

template <typename T>
size_t Queue<T>::size() const
{
    return count;
}

#endif  //__MY_QUEUE_H__